package main

import (
	"fmt"
	"math"
)

func maxProductPath1(grid [][]int) int {
	m,n:=len(grid),len(grid[0])
	mag,mng:=make([][]int64,m),make([][]int64,m)
	for i,_:= range mag{
		mag[i]=make([]int64,n)
		mng[i]=make([]int64,n)
	}
	mng[0][0]=int64(grid[0][0])
	mag[0][0]=mng[0][0]
	
	for i:=1;i<m;i++{
		mng[i][0]=mag[i-1][0]*int64(grid[i][0])
		mag[i][0]=mng[i][0]
	}
	for i:=1;i<n;i++{
		mng[0][i]=mag[0][i-1]*int64(grid[0][i])
		mag[0][i]=mng[0][i]
	}
	for i:=1;i<m;i++{
		for j:=1;j<n;j++{
			if grid[i][j] >=0{
				mag[i][j]=int64(math.Max(float64(mag[i-1][j]),float64(mag[i][j-1])))*int64(grid[i][j])
				mng[i][j]=int64(math.Min(float64(mng[i-1][j]),float64(mng[i][j-1])))*int64(grid[i][j])
			}else{
				mag[i][j]=int64(math.Min(float64(mng[i-1][j]),float64(mng[i][j-1])))*int64(grid[i][j])
				mng[i][j]=int64(math.Max(float64(mag[i-1][j]),float64(mag[i][j-1])))*int64(grid[i][j])
			}
		}
	}
	if mag[m-1][n-1]<0{
		return -1
	}
	return int(mag[m-1][n-1]%(1e9+7))
}

func maxProductPath2(grid [][]int) int {
	var (
		rows = len(grid)
		cols = len(grid[0])
		dp   = make([][][2]int, rows)
		gen  func(ch chan int, a int, b ...[2]int) chan int
	)
	gen = func(ch chan int, a int, b ...[2]int) chan int {
		for _, v := range b {
			ch <- a * v[0]
			ch <- a * v[1]
		}
		close(ch)
		return ch
	}

	for i := 0; i < rows; i++ {
		dp[i] = make([][2]int, cols)
	}
	dp[0][0][0], dp[0][0][1] = grid[0][0], grid[0][0]

	for i := 1; i < rows; i++ {
		t := dp[i-1][0][0] * grid[i][0]
		dp[i][0][0], dp[i][0][1] = t, t
	}

	for i := 1; i < cols; i++ {
		t := dp[0][i-1][0] * grid[0][i]
		dp[0][i][0], dp[0][i][1] = t, t
	}

	for i := 1; i < rows; i++ {
		for j := 1; j < cols; j++ {
			mi := grid[i][j] * dp[i-1][j][0]
			ma := mi // init min, max

			for v := range gen(make(chan int, 4), grid[i][j], dp[i-1][j], dp[i][j-1]) {
				if v < mi {
					mi = v
				}
				if v > ma {
					ma = v
				}
			}
			dp[i][j][0], dp[i][j][1] = mi, ma
		}
	}

	if dp[rows-1][cols-1][1] < 0 {
		return -1
	}
	return dp[rows-1][cols-1][1] % 1000000007
}

func maxProductPath(grid [][]int) int {
    var(
        nr int = len(grid)
        nc int = len(grid[0])
        ans int = math.MinInt64
        dfs func(int, int, int)
    )
    dfs = func(row, col, value int) {
        value *= grid[row][col]
        if value == 0 || row == nr-1 && col == nc-1 {
            if value > ans {
                ans = value
            }
            return
        }
        if col < nc - 1 {
            dfs(row, col+1, value)
        }
        if row < nr - 1 {
            dfs(row+1, col, value)
        }
    }
    dfs(0, 0, 1)
    if ans < 0 {
        return -1
    } else {
        return ans % 1000000007
    }
}

func main(){
	fmt.Println("hello")
	v:=[][]int{[]int{1,-2,1},[]int{1,-2,1},[]int{3,-4,1}}
	fmt.Println(maxProductPath(v))
}